SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Rocchio algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Rocchio algorithm</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>The <b>Rocchio algorithm</b> is based on a method of <a href="Relevance_feedback" title="Relevance feedback">relevance feedback</a> found in <a href="Information_retrieval" title="Information retrieval">information retrieval</a> systems which stemmed from the <a href="SMART_Information_Retrieval_System" title="SMART Information Retrieval System">SMART Information Retrieval System</a> developed between 1960 and 1964. Like many other retrieval systems, the Rocchio <a href="Algorithm" title="Algorithm">algorithm</a> was developed using the <a href="Vector_space_model" title="Vector space model">vector space model</a>. Its underlying assumption is that most users have a general conception of which documents should be denoted as <a href="Relevance_(information_retrieval)" title="Relevance (information retrieval)">relevant</a> or irrelevant.<sup id="cite_ref-ir-manning_1-0" class="reference"><a href="#cite_note-ir-manning-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Therefore, the user's search query is revised to include an arbitrary percentage of relevant and irrelevant documents as a means of increasing the <a href="Search_engine" title="Search engine">search engine</a>'s <a href="Information_retrieval#Recall" title="Information retrieval">recall</a>, and possibly the precision as well. The number of relevant and irrelevant documents allowed to enter a <a href="Information_retrieval" title="Information retrieval">query</a> is dictated by the so called <a href="Weight_(mathematics)" class="mw-redirect" title="Weight (mathematics)">weights</a>, i.e. the variables <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span> listed below in the <a href="Rocchio_Classification" class="mw-redirect" title="Rocchio Classification">Algorithm section</a>.<sup id="cite_ref-ir-manning_1-1" class="reference"><a href="#cite_note-ir-manning-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<p>The <a href="Formula_(mathematical_logic)" class="mw-redirect" title="Formula (mathematical logic)">formula</a> and variable definitions for Rocchio relevance feedback are as follows:<sup id="cite_ref-ir-manning_1-2" class="reference"><a href="#cite_note-ir-manning-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {Q}}_{m}=a\,{\vec {Q}}_{o}+b\,{\frac {1}{|D_{r}|}}\sum _{{\vec {D}}_{j}\in D_{r}}{\vec {D}}_{j}-c\,{\frac {1}{|D_{nr}|}}\sum _{{\vec {D}}_{k}\in D_{nr}}{\vec {D}}_{k}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {Q}}_{m}=a\,{\vec {Q}}_{o}+b\,{\frac {1}{|D_{r}|}}\sum _{{\vec {D}}_{j}\in D_{r}}{\vec {D}}_{j}-c\,{\frac {1}{|D_{nr}|}}\sum _{{\vec {D}}_{k}\in D_{nr}}{\vec {D}}_{k}}</annotation>

</semantics>

</math></span><img src="./6aab65a36d95bfc3a439cdc80711c1aecaa1d0d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.171ex; width:49.535ex; height:7.509ex;" alt="{\displaystyle {\vec {Q}}_{m}=a\,{\vec {Q}}_{o}+b\,{\frac {1}{|D_{r}|}}\sum _{{\vec {D}}_{j}\in D_{r}}{\vec {D}}_{j}-c\,{\frac {1}{|D_{nr}|}}\sum _{{\vec {D}}_{k}\in D_{nr}}{\vec {D}}_{k}}" loading="lazy"></span>

</p>

<th>Variable

</th>

<th>Value

</th></tr>

<tr>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {Q}}_{m}}</annotation>

</semantics>

</math></span><img src="./7c308d5387c8bcdef20bec9a51f31637eb311777.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.513ex; height:3.509ex;" alt="{\displaystyle {\vec {Q}}_{m}}" loading="lazy"></span>

</td>

<td>Modified query vector

</td></tr>

<tr>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {Q}}_{o}}</annotation>

</semantics>

</math></span><img src="./f848b3b2f54cc26d6cfda1198cb66d940b49b6e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.868ex; height:3.509ex;" alt="{\displaystyle {\vec {Q}}_{o}}" loading="lazy"></span>

</td>

<td>Original query vector

</td></tr>

<tr>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {D}}_{j}}</annotation>

</semantics>

</math></span><img src="./8c7548e716decd6307b7258bedbe2abcf5ee5efd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.834ex; height:3.509ex;" alt="{\displaystyle {\vec {D}}_{j}}" loading="lazy"></span>

</td>

<td>Related document vector

</td></tr>

<tr>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {D}}_{k}}</annotation>

</semantics>

</math></span><img src="./3988042a0ab098a0abb8582b9b78014dd35e1e45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.013ex; height:3.176ex;" alt="{\displaystyle {\vec {D}}_{k}}" loading="lazy"></span>

</td>

<td>Non-related document vector

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span>

</td>

<td>Original query weight

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span>

</td>

<td>Related documents weight

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span>

</td>

<td>Non-related documents weight

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{r}}</annotation>

</semantics>

</math></span><img src="./8783bccae1e365d5e58cd502bea46ce4eee7fe34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.898ex; height:2.509ex;" alt="{\displaystyle D_{r}}" loading="lazy"></span>

</td>

<td>Set of related documents

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{nr}}</annotation>

</semantics>

</math></span><img src="./2f27111d91e1f763efbaec742d73bf93f4dbac03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.884ex; height:2.509ex;" alt="{\displaystyle D_{nr}}" loading="lazy"></span>

</td>

<td>Set of non-related documents

</td></tr></tbody></table>

<p>As demonstrated in the formula, the associated weights (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span>) are responsible for shaping the modified <a href="Vector_space" title="Vector space">vector</a> in a direction closer, or farther away, from the original query, related documents, and non-related documents. In particular, the values for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span> should be incremented or decremented proportionally to the set of documents classified by the user. If the user decides that the modified query should not contain terms from either the original query, related documents, or non-related documents, then the corresponding weight (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span>) value for the category should be set to 0.

</p><p>In the later part of the algorithm, the variables <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{r}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{r}}</annotation>

</semantics>

</math></span><img src="./8783bccae1e365d5e58cd502bea46ce4eee7fe34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.898ex; height:2.509ex;" alt="{\displaystyle D_{r}}" loading="lazy"></span>, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{nr}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{nr}}</annotation>

</semantics>

</math></span><img src="./2f27111d91e1f763efbaec742d73bf93f4dbac03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.884ex; height:2.509ex;" alt="{\displaystyle D_{nr}}" loading="lazy"></span> are presented to be sets of <a href="Tuple" title="Tuple">vectors</a> containing the coordinates of related documents and non-related documents. In the formula, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {D}}_{j}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {D}}_{j}}</annotation>

</semantics>

</math></span><img src="./8c7548e716decd6307b7258bedbe2abcf5ee5efd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.834ex; height:3.509ex;" alt="{\displaystyle {\vec {D}}_{j}}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {D}}_{k}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {D}}_{k}}</annotation>

</semantics>

</math></span><img src="./3988042a0ab098a0abb8582b9b78014dd35e1e45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.013ex; height:3.176ex;" alt="{\displaystyle {\vec {D}}_{k}}" loading="lazy"></span> are the vectors used to iterate through the two sets <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{r}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{r}}</annotation>

</semantics>

</math></span><img src="./8783bccae1e365d5e58cd502bea46ce4eee7fe34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.898ex; height:2.509ex;" alt="{\displaystyle D_{r}}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{nr}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{nr}}</annotation>

</semantics>

</math></span><img src="./2f27111d91e1f763efbaec742d73bf93f4dbac03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.884ex; height:2.509ex;" alt="{\displaystyle D_{nr}}" loading="lazy"></span> and form vector <a href="Summation" title="Summation">summations</a>. These sums are normalized, i.e. divided by the size of their respective document set.

</p><p>In order to visualize the changes taking place on the modified vector, please refer to the image below.<sup id="cite_ref-ir-manning_1-3" class="reference"><a href="#cite_note-ir-manning-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> As the weights are increased or decreased for a particular category of documents, the coordinates for the modified vector begin to move either closer, or farther away, from the <a href="Centroid" title="Centroid">centroid</a> of the document collection. Thus if the weight is increased for related documents, then the modified vectors <a href="Coordinate" class="mw-redirect" title="Coordinate">coordinates</a> will reflect being closer to the centroid of related documents.

</p>

<div class="mw-heading mw-heading2"><h2 id="Time_complexity">Time complexity</h2></div>

<th>Variable

</th>

<th>Value

</th></tr>

<tr>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {D} }</annotation>

</semantics>

</math></span><img src="./b932b553742ca27776057f1262527014ebbb46a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {D} }" loading="lazy"></span>

</td>

<td>Labeled document set

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{ave}}</annotation>

</semantics>

</math></span><img src="./75b4369c971dc7be38491bea72cddf2276d913c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.248ex; height:2.509ex;" alt="{\displaystyle L_{ave}}" loading="lazy"></span>

</td>

<td>Average tokens per document

</td></tr>

<tr>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {C} }</annotation>

</semantics>

</math></span><img src="./f9add4085095b9b6d28d045fd9c92c2c09f549a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {C} }" loading="lazy"></span>

</td>

<td>Class set

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math></span><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"></span>

</td>

<td>Vocabulary/term set

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L_{a}}</annotation>

</semantics>

</math></span><img src="./87a7bf511194a88867e63c66594f8c06f106bbbb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.685ex; height:2.509ex;" alt="{\displaystyle L_{a}}" loading="lazy"></span>

</td>

<td>Number of tokens in document

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{a}}</annotation>

</semantics>

</math></span><img src="./3952acec4181822fdb8e2a1ade89550d85b569e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.356ex; height:2.509ex;" alt="{\displaystyle M_{a}}" loading="lazy"></span>

</td>

<td>Number of types in document

</td></tr></tbody></table>

<p>The <a href="Time_complexity" title="Time complexity">time complexity</a> for training and testing the algorithm are listed below and followed by the definition of each <a href="Variable_(mathematics)" title="Variable (mathematics)">variable</a>. Note that when in testing phase, the time complexity can be reduced to that of calculating the <a href="Euclidean_distance" title="Euclidean distance">euclidean distance</a> between a class <a href="Centroid" title="Centroid">centroid</a> and the respective document. As shown by: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (\vert \mathbb {C} \vert M_{a})}">

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (\vert \mathbb {C} \vert M_{a})}</annotation>

</semantics>

</math></span><img src="./b63c73d07980be78f5f2788cbc9554a43a636b25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.945ex; height:2.843ex;" alt="{\displaystyle \Theta (\vert \mathbb {C} \vert M_{a})}" loading="lazy"></span>.

</p><p>Training = <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )}</annotation>

</semantics>

</math></span><img src="./39077c847946ddd84ee64c6bc9d5c059c48a9ef6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.73ex; height:2.843ex;" alt="{\displaystyle \Theta (\vert \mathbb {D} \vert L_{ave}+\vert \mathbb {C} \vert \vert V\vert )}" loading="lazy"></span> <br>

Testing = <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})}">

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})}</annotation>

</semantics>

</math></span><img src="./eb1717c749d09be068fca3f7e0dfb5f1ff5444db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.514ex; height:2.843ex;" alt="{\displaystyle \Theta (L_{a}+\vert \mathbb {C} \vert M_{a})=\Theta (\vert \mathbb {C} \vert M_{a})}" loading="lazy"></span> <sup id="cite_ref-ir-manning_1-4" class="reference"><a href="#cite_note-ir-manning-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Usage">Usage</h2></div>

<p>Though there are benefits to ranking documents as not-relevant, a <a href="https://en.wiktionary.org/wiki/relevant" class="extiw external" title="wikt:relevant">relevant</a> document ranking will result in more precise documents being made available to the user. Therefore, traditional values for the algorithm's weights (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span>) in <a href="Nearest_centroid_classifier" title="Nearest centroid classifier">Rocchio classification</a> are typically around <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> = 1, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> = 0.8, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span> = 0.1. Modern <a href="Information_retrieval" title="Information retrieval">information retrieval</a> systems have moved towards eliminating the non-related documents by setting c = 0 and thus only accounting for related documents. Although not all <a href="Information_retrieval" title="Information retrieval">retrieval systems</a> have eliminated the need for non-related documents, most have limited the effects on modified query by only accounting for strongest non-related documents in the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{nr}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{nr}}</annotation>

</semantics>

</math></span><img src="./2f27111d91e1f763efbaec742d73bf93f4dbac03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.884ex; height:2.509ex;" alt="{\displaystyle D_{nr}}" loading="lazy"></span> set.

</p>

<div class="mw-heading mw-heading2"><h2 id="Limitations">Limitations</h2></div>

<p>The Rocchio algorithm often fails to classify multimodal classes and relationships. For instance, the country of <a href="Burma" class="mw-redirect" title="Burma">Burma</a> was renamed to <a href="Myanmar" title="Myanmar">Myanmar</a> in 1989. Therefore, the two queries of "Burma" and "Myanmar" will appear much farther apart in the <a href="Vector_space_model" title="Vector space model">vector space model</a>, though they both contain similar origins.<sup id="cite_ref-ir-manning_1-5" class="reference"><a href="#cite_note-ir-manning-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Nearest_centroid_classifier" title="Nearest centroid classifier">Nearest centroid classifier</a>, aka Rocchio classifier</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-ir-manning-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-ir-manning_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-ir-manning_1-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-ir-manning_1-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-ir-manning_1-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-ir-manning_1-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-ir-manning_1-5"><sup><i><b>f</b></i></sup></a></span> <span class="reference-text">Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze: <i>An Introduction to Information Retrieval</i>, page 163-167. Cambridge University Press, 2009.</span>

</li>

</ol></div></div>

<ul><li><a rel="nofollow" class="external text" href="http://sigir.org/files/museum/pub-08/XXIII-1.pdf">Relevance Feedback in Information Retrieval</a></li>

<li><a rel="nofollow" class="external text" href="http://nlp.stanford.edu/IR-book/pdf/09expand.pdf">Relevance Feedback and Query Expansion</a></li>

<li><a rel="nofollow" class="external text" href="http://nlp.stanford.edu/IR-book/pdf/14vcat.pdf">Vector Space Classification</a></li>

<li><a rel="nofollow" class="external text" href="http://cs.nyu.edu/courses/fall07/G22.2580-001/lec7.html">Data Classification</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-09-09" href="https://en.wikipedia.org/wiki/?title=Rocchio_algorithm&oldid=1244862056">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>